package 题目集.bfs.双向bfs;

import org.junit.Test;

import java.util.*;

/**
 * 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
 * 每一对相邻的单词只差一个字母。
 *  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
 * sk == endWord
 * 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
 * https://leetcode.cn/problems/word-ladder/
 */
public class 单词接龙 {
    /**
     * 传统bfs中，我们是从一个点开始，一层一层的向外扩展，直到找到目标点。
     * 双向bfs是从起点和终点同时开始，一层一层的向外扩展，只保留当前层和下一层，直到两个方向相遇。
     * 本题思路：
     *      枚举每一个字符，将其替换为26个字母，看是否在wordList中，如果在，则加入队列。
     *      从beginWord和endWord同时开始，一层一层的向外扩展，直到两个方向相遇。
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);    //转换为set，加快查找速度
        if (!wordSet.contains(endWord)) return 0; //endWord不在wordList中，直接返回0
        int res = 0;
        Set<String> smallSet = new HashSet<>(), moreSet = new HashSet<>();    //双向bfs的起点和终点
        Set<String> nextSet = new HashSet<>();  //下一层
        smallSet.add(beginWord);
        moreSet.add(endWord);
        while (!smallSet.isEmpty() && !moreSet.isEmpty()) {
            res++;
            wordSet.removeAll(smallSet);   //这里移除相当于bfs的标志已访问
            for (String string : smallSet) {    //出队列
                if (moreSet.contains(string)) return res;   //是否等于终点，如果是步数的话要-1，但这里是左闭右闭
//                wordSet.remove(string);     //不能在这里移除，因为可能存在同层指向同层的情况，会导致下一层多添加一次当前层的内容，应该在上面removeAll（移除当前层）
                char[] chars = string.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    char old = chars[i];
                    for (char j = 'a'; j <= 'z'; j++) {     //这题单词的长度很短，所以可以枚举字符串的每个字符
                        chars[i] = j;
                        String newString = new String(chars);
                        if (wordSet.contains(newString)) {
                            nextSet.add(newString);
                        }
                    }
                    chars[i] = old;
                }
            }
            smallSet=nextSet;
            if (smallSet.size()>moreSet.size()){
                Set<String> temp=moreSet;
                moreSet=smallSet;
                smallSet=temp;
            }
            nextSet=new HashSet<>();
        }
        return 0;
    }
    @Test
    public void test(){
        String[] words={"hot", "dot", "dog", "lot", "log", "cog"};
        System.out.println(ladderLength("pog", "cog", Arrays.asList(words)));
    }
}
